/////////////////////////////////////////////////////////////////////////
//
// Amuse Engine SDK - core/algorithm
// Copyright( c) 2013.  All Rights Reserved
//
// File:		AEQuickSort.cpp
// Author:		Gianluca Belardelli
// Date:		04/10/2013
//
/////////////////////////////////////////////////////////////////////////
#include <AECore.h>
#include <core/algorithm/IAEComparator.h>
#include <core/algorithm/IAESorter.h>
#include <core/algorithm/AEQuickSort.h>

void AEQuickSort::_quickSort( void *lpArray, int nLeft, int nRight, IAEComparator *lpComparator )
{
    if ( nRight <= nLeft ) return;
    int i = _partition( lpArray, nLeft, nRight, lpComparator );
    _quickSort( lpArray, nLeft, i - 1, lpComparator);
    _quickSort( lpArray, i + 1, nRight, lpComparator);
}

int AEQuickSort::_partition( void *lpArray, int nLeft, int nRight, IAEComparator *lpComparator )
{
    int i = nLeft - 1;
    int j = nRight;
  /*  IBaseObject **lpA = (IBaseObject **)lpArray;
	IBaseObject *lpSwap;

	while (true) 
	{
        while ( lpComparator->Compare( lpA[++i], lpA[nRight] ) < 0 );

		while ( lpComparator->Compare( lpA[nRight], lpA[--j] ) < 0 ) 
		{    // find item on right to swap
            if ( j == nLeft ) 
                break;                 // don't go out-of-bounds
        }

		if (i >= j)
            break;                     // check if pointers cross

		lpSwap = lpA[i];              // swap two elements into place
        lpA[i] = lpA[j];
        lpA[j] = lpSwap;
    }

    lpSwap = lpA[i]; // swap with partition element
    lpA[i] = lpA[nRight];
    lpA[nRight] = lpSwap;
	*/
    return i;
}

void AEQuickSort::Sort( void *lpArray, int nCount, IAEComparator *lpComparator )
{
	_quickSort( lpArray, 0, nCount - 1, lpComparator );
};